﻿// Author: Liep Nguyen, 10:44 PM 3/10/2013
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RoutingAlgorithms
{
    class Dijikstra
    {
        public static int[] GetShortestPath(Topology topology, int s)
        {
            int n = topology.Nodes.Count;
            double[] d = new double[n];
            int[] pre = new int[n];
            
            // Initialize
            for (int v = 0; v < n; v++)
            {
                d[v] = double.MaxValue;
                pre[v] = s;
            }

            d[s] = 0;
            List<Node> T = new List<Node>(topology.Nodes);

            while (T.Count > 0)
            {
                // Find node u within T set, where d[u] = min{d[z]:z within T set}
                int u = T[0].Id;
                foreach (Node node in T)
                    if (d[node.Id] < d[u])
                        u = node.Id;

                T.Remove(topology.Nodes[u]);

                // Browse all adjacent node to update distance from s.
                foreach (Link link in topology.Nodes[u].Links)
                {
                    int v = link.Destination.Id;
                    if (d[v] > d[u] + link.Cost)
                    {
                        d[v] = d[u] + link.Cost;
                        pre[v] = u;
                    }
                }
            }
            return pre;
        }
    }
}
